Das RSA-Verfahren war das erste Public-Key-Verschlüsselungsverfahren und ist auch heute noch das wichtigste. Es baut auf der Schwierigkeit auf, große Zahlen in ihre Primfaktoren zu zerlegen.

\subsubsection{Schlüsselerzeugung}

Nachfolgend wird beschrieben, wie der private Schlüssel $d$ und der öffentliche Schlüssel $(n, e)$ ermittelt werden. Die  Zahl $n$ bezeichnet man als \textbf{RSA-Modul}, $e$ als \textbf{Verschlüsselungsexponenten} und $d$ als \textbf{Entschlüsselungsexponenten}.

\begin{enumerate}

\item Zwei Primzahlen $p$ und $q$ auswählen.

\item Berechnung des RSA-Modul $n = p \cdot q$.

\item Auswahl des Verschlüsselungsexponenten $e \in \mathbb{N}$ mit $1 < e < \varphi = (p - 1) \cdot (q - 1)$ und $gcd(e, (p - 1) \cdot (q - 1)) = 1$. Berechnet wird er mit Hilfe des erweiterten euklidischen Algorithmus. Wichtig ist, dass $e$ immer ungerade ist.

\item Berechnung des Entschlüsselungsexponenten $d$ mit $1 < d < (p - 1) \cdot (q - 1)$ und $d \cdot e \equiv 1 \tmod (p - 1) \cdot (q - 1)$. Die Zahl $d$ existiert, weil $gcd(e, (p - 1) \cdot (q - 1)) = 1$. Die Auflösung erfolgt durch Anwendung des erweiterten euklidischen Algorithmus.

\end{enumerate}

\textbf{Beispiel}

Die einzelnen Arbeitsschritte werden anhand von Beispiel \buchmann{9.3.1} veranschaulicht. Als Primzahlen wählt man $p = 11$ und $q = 23$. Somit ergibt sich als RSA-Modul die Zahl $n = p \cdot q = 11 \cdot 23 = 253$.

\begin{center}
\uline{$n = 253$}
\end{center}

Für den Verschlüsselungsexponenten $e$ gilt $(p - 1) \cdot (q - 1) = 10 \cdot 22 = 220$ und deshalb $1 < e < 220$ mit $gcd(e, 220) = 1$. Die kleinste Zahl, auf die das zutrifft, ist

\begin{center}
\uline{$e = 3$}
\end{center}

Der Entschlüsselungsexponent muss die Bedingung $1 < d < 220$ und $3 \cdot d \equiv 1 \tmod 220$ erfüllen. Letzteres ist gleichbedeutend mit $220 \cdot \mathbb{Z} + 3 \cdot d = 1$ und kann allgemeingültig auch als $a \cdot x + b \cdot y = 1$ mit $a = 220$, $b = 3$ und $y = d$ ausgedrückt werden. Die Auflösung erfolgt durch Anwendung des erweiterten euklidischen Algorithmus.

\begin{center}
\begin{tabular}{|c|cccc|}
\hline
$k$ & $0$ & $1$ & $2$ & $3$ \\
\hline
$r_k$ & $220$ & $3$ & $1$ & $0$ \\
$q_k$ & & $73$ & $3$ & \\
$x_k$ & $1$ & $0$ & \cellcolor{dunkelgrau}$1$ & $3$ \\
$y_k$ & $0$ & $1$ & \cellcolor{dunkelgrau}$73$ & $220$ \\
\hline 
\end{tabular}
\end{center}

Folglich gilt $220 \cdot 1 + 3 \cdot (-73) = 1$, wobei $d = y = -73 \tmod 220 \equiv 147 \tmod 220$. Der Entschlüsselungsexponent ist also

\begin{center}
\uline{$d = 147$}
\end{center}

Zusammenfassend gilt für den öffentlichen Schlüssel $(n, e)$ und den privaten Schlüssel $d$

\begin{center}
\uuline{$(n, e) = (253, 3)$} und \uuline{$d = 147$}
\end{center}


\subsubsection{Verschlüsselung}

Zur Verschlüsselung von Zahlen besteht der Klartextraum aus allen $m \in \mathbb{N}$ mit $0 \le m < n$. Der Klartext $m$ wird verschlüsselt zu $c = m ^ e \tmod n$. Somit kann jeder, der den öffentlichen Schlüssel $(n, e)$ kennt, eine Nachricht verschlüsseln. Die Berechnung erfolgt mit Hilfe der schnellen Exponentiation.

\begin{center}
$c = m ^ e \tmod n$
\end{center}

\textbf{Beispiel}

Die einzelnen Arbeitsschritte werden anhand von Beispiel \buchmann{9.3.2} veranschaulicht. Wie im vorigen Kapitel berechnet ist der öffentliche Schlüssel $(n, e) = (253, 3)$. Verschlüsselt wird der Klartext $m = 165$.

Der Klartextraum ist $0 \le m < n$ mit $m \in \mathbb{N}$. Für den Klartext $m = 165$ gilt deshalb $c = 165 ^ 3 \tmod 253$. Die Berechnung erfolgt mit Hilfe der schnellen Exponentiation. Die Binärentwicklung des Exponenten kann leicht ermittelt werden und lautet $3 = 2 ^ 1 + 2 ^ 0$. Anschließend werden die sukzessiven Quadrate in $\mathbb{Z}/253\mathbb{Z}$ berechnet.

\begin{center}
\begin{tabular}{|c||c|}
\hline
\cellcolor{dunkelgrau}$165^{2^0}$ & \cellcolor{dunkelgrau}$165^{2^1}$ \\
\hline
\cellcolor{dunkelgrau}$165$ & \cellcolor{dunkelgrau}$165^2 \equiv 154$ \\
\hline 
\end{tabular}
\end{center}

Folglich gilt $c = 165 ^ 3 \tmod 253 = 165 ^ {2 ^ 1} \cdot 165 ^ {2 ^ 0} \tmod 253 \equiv 154 \cdot 165 \equiv 110 \tmod 253$. Der Klartext $m = 165$ wird folglich zum Chiffretext

\begin{center}
\uuline{$c = 110$}
\end{center}

Mit der RSA-Verschlüsselungsmethode kann eine Art \textbf{Blockchiffre} realisiert werden. Geht man davon aus, dass das Alphabet $\Sigma$ genau $N = |\Sigma|$  Zeichen hat, so gilt $k = \lfloor \log_{N}n \rfloor$.

Ein Block $m_1, m_2 ... m_k$ mit $m_i \in \Sigma$ und $1 \le i \le k$ wird in die Zahl $m = \sum_{i = 1} ^ k m_i \cdot N^ {k - i}$ umgewandelt. Wegen $k = \lfloor \log_{N}n \rfloor$ gilt $0 \le m \le (N - 1) \sum_{i = 1} ^ k N ^ {k - i} = N ^ k - 1 < n$. Anschließend wird durch $c = m ^ e \tmod n$ verschlüsselt.

Dann wird die $N$-adische Entwicklung von $c$ ermittelt, die eine Länge von $k + 1$ haben kann. Es gilt $c = \sum_{i = 0} ^ k c_i \cdot N ^ {k - 1}$ mit $c_i \in \Sigma$ und $0 \le i \le k$. Der Schlüsselblock ist somit $c = c_0 \cdot c_1 \cdot ... \cdot c_k$.

Man sieht, dass RSA Blöcke der Länge $k$ injektiv auf Blöcke der Länge $k + 1$ abbildet. Es handelt sich aber um nicht um eine Blockchiffre im Sinne der bekannten Definition. Trotzdem können durch eine kleine Modifikation der ECB- und CBC-Mode angewendet werden. Für den CFB- oder OFB-Mode ist das nicht möglich, weil beide die Verschlüsselungsfunktion nutzen, die in diesem Fall öffentlich bekannt ist.

\textbf{Beispiel}

Nachfolgend wird RSA-Verschlüsselungsmethode anhand von Beispiel \buchmann{9.3.3} als eine Art Blockchiffre angewandt. Wie in den vorherigen Beispielen ist der öffentliche Schlüsse $(n, e) = (253, 3)$. Man verwendet das Alphabet $\Sigma = {0, a, b, c}$ mit Abbildungsvorschrift aus Tabelle \ref{abbildungsvorschrift}. Verschlüsselt wird der Klartext $abb$.

\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
0 & a & b & c \\
\hline
0 & 1 & 2 & 3 \\
\hline 
\end{tabular}
\end{center}
\caption{Abbildungsvorschrift für das Alphabet $\Sigma = {0, a, b, c}$}
\label{abbildungsvorschrift}
\end{table}

Im ersten Schritt wird $k = \lfloor \log_{N} n \rfloor$ ist $k = \lfloor \log_{4} 253 \rfloor = 3$ berechnet. Somit ist die Länge der Klartextblöcke

\begin{center}
\uline{$k = 3$}
\end{center}

Wendet man die Abbildungsvorschrift aus Tabelle \ref{abbildungsvorschrift} auf den Klartext $abb$ an, so erhält man $m_1 = 1$ (a), $m_2 = 2$ (b) und $m_3 = 2$ (b). Da der Klartext genau drei Zeichen lang ist, wird genau ein Block verschlüsselt. Es gilt $c = \sum_{i = 0} ^ k c_i \cdot N ^ {k - 1} = m_1 \cdot N ^ {k - 1} + m_2 \cdot N ^ {k - 2} + m_3 \cdot N ^ {k - 3} = 1 \cdot 4 ^ {3 - 1} + 2 \cdot 4 ^ {3 - 2} + 2 \cdot 4 ^ {3 - 3} = 26$. Der Klartext $abb$ entspricht folglich der Zahl

\begin{center}
\uline{$m = 26$}
\end{center}

Für den Chiffretext gilt $c = m ^ e \tmod n$ mit $m = 26$, $e = 3$ und $n = 253$. Die Verschlüsselung erfolgt mit $c = 26 ^ 3 \tmod 253$ und wird mit Hilfe der schnellen Exponentiation aufgelöst. Die Binärentwicklung des Exponenten ist $3 = 2 ^ 1 + 2 ^ 0$. Anschließend berechnet man die sukzessiven Quadrate in $\mathbb{Z}/253\mathbb{Z}$.

\begin{center}
\begin{tabular}{|c||c|}
\hline
\cellcolor{dunkelgrau}$26^{2^0}$ & \cellcolor{dunkelgrau}$26^{2^1}$ \\
\hline
\cellcolor{dunkelgrau}$26$ & \cellcolor{dunkelgrau}$26^2 \equiv 170$ \\
\hline 
\end{tabular}
\end{center}

Daraus folgt, dass $26 ^ 3 \tmod 253 = 26 ^ {2 ^ 1} \cdot 26 ^ {2 ^ 0} \tmod 253 \equiv 26 \cdot 170 \tmod 253 \equiv 119 \tmod 253$. Deshalb ist

\begin{center}
\uline{$c = 119$}
\end{center}

Die Länge der $N$-adischen Entwicklung von $c$ ist $k = \lfloor log_{N} c \rfloor + 1 = \lfloor log_{4} 119 \rfloor + 1 = 3 + 1 = 4$. Die Berechnung erfolgt mit Hilfe von Tabelle \ref{n_adische_entwicklung_blockchiffre}.

\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
$i$ & 1 & 2 & 3 & 4 \\
\hline
$g ^ {k - i}$ & $4 ^ {4 - 1} = 64$ & $4 ^ {4 - 2} = 16$ & $4 ^ {4 - 3} = 4$ & $4 ^ {4 - 4} = 1$ \\
\hline 
\cellcolor{dunkelgrau}$a_i$ & \cellcolor{dunkelgrau}$\lfloor \frac{119}{64} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{55}{16} \rfloor = 3$ & \cellcolor{dunkelgrau}$\lfloor \frac{7}{4} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{1} \rfloor = 3$ \\
\hline
$a_i \cdot g ^ {k - i}$ & $1 \cdot 64 = 64$ & $3 \cdot 16 = 48$ & $1 \cdot 4 = 4$ & $3 \cdot 1 = 3$ \\
\hline
$a - \sum_{j = 1} ^ i a_j \cdot g ^ {k - j}$ & $119 - 64 = 55$ & $55 - 48 = 7$ & $7 - 4 = 3$ & $3 - 3 = 0$ \\
\hline
\end{tabular}
\end{center}
\caption{Berechnung der $N$-adischen Entwicklung von $c$}
\label{n_adische_entwicklung_blockchiffre}
\end{table}

Die $N$-adische Entwicklung ist folglich $c = 119 = 1 \cdot 4 ^ 3 + 3 \cdot 4 ^ 2 + 1 \cdot 4 ^ 1 + 3 \cdot 4 ^ 0$ mit $c_1 = 1$ (a), $c_2 = 3$ (c), $c_3 = 1$ (a) und $c_4 = 3$ (c).

\begin{center}
\uuline{Der Chiffretextblock zu abb ist acac}
\end{center}

\subsubsection{Entschlüsselung}

Wenn $(n, e)$ der öffentliche und $d$ der private Schlüssel ist, so gilt für den Klartext $m = (m ^ e) ^ d \tmod n = c ^ d \tmod n$.

\begin{center}
$m = c ^ d \tmod n$
\end{center}

\textbf{Beispiel}

In Beispiel \buchmann{9.3.5} wird die Entschlüsselung aufbauend auf dem bisher verwendeten Beispiel durchgeführt. Es gilt $d = 147$ und $c = 119$. Den Klartext erhält man durch die Berechnung von $m = 119 ^ {147} \tmod 253$. Hierfür bedient man sich der schnellen Exponentiation.

Die Länge der Binärentwicklung des Exponenten $147$ ist $k = \lfloor log_{2} 147 \rfloor + 1 = 8$. Die Bestimmung der Binärentwicklung erfolgt mit Hilfe von Tabelle \ref{binaerentwicklung_147}.

\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
$i$ & 1 & 2 & 3 & 4 \\
\hline
$g ^ {k - i}$ & $2 ^ 7$ & $2 ^ 6$ & $2 ^ 5$ & $2 ^ 4 = 1$ \\
\hline 
\cellcolor{dunkelgrau}$a_i$ & \cellcolor{dunkelgrau}$\lfloor \frac{147}{2 ^ 7} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{19}{2 ^ 6} \rfloor = 0$ & \cellcolor{dunkelgrau}$\lfloor \frac{19}{2 ^ 5} \rfloor = 0$ & \cellcolor{dunkelgrau}$\lfloor \frac{19}{2 ^ 4} \rfloor = 1$ \\
\hline
$a_i \cdot g ^ {k - i}$ & $2 ^ 7$ & $0$ & $0$ & $2 ^ 4$ \\
\hline
$a - \sum_{j = 1} ^ i a_j \cdot g ^ {k - j}$ & $147 - 2 ^ 7 = 19$ & $19$ & $19$ & $19 - 2 ^ 4 = 3$ \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
$i$ & 5 & 6 & 7 & 8 \\
\hline
$g ^ {k - i}$ & $2 ^ 3$ & $2 ^ 2$ & $2 ^ 1$ & $2 ^ 0$ \\
\hline 
\cellcolor{dunkelgrau}$a_i$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{2 ^ 3} \rfloor = 0$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{2 ^ 2} \rfloor = 0$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{2 ^ 1} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{1}{2 ^ 1} \rfloor = 1$ \\
\hline
$a_i \cdot g ^ {k - i}$ & $0$ & $0$ & $2$ & $1$ \\
\hline
$a - \sum_{j = 1} ^ i a_j \cdot g ^ {k - j}$ & $3$ & $3$ & $3 - 2 = 1$ & $1 - 1 = 0$ \\
\hline
\end{tabular}
\end{center}
\caption{Ermittlung der Binärentwicklung von $147$}
\label{binaerentwicklung_147}
\end{table}

Somit ergibt sich die Binärentwicklung als 

\begin{center}
\uline{$147 = 2 ^ 7 + 2 ^ 4 + 2 ^ 1 + 2 ^ 0$.}
\end{center}

Anschließend werden die sukzessiven Quadrate in $\mathbb{Z}/253\mathbb{Z}$ ermittelt.

\begin{center}
\begin{tabular}{|c||c||c||c||c||c||c||c|}
\hline
\cellcolor{dunkelgrau}$119^{2^0}$ & \cellcolor{dunkelgrau}$119^{2^1}$ & $119^{2^2}$ & $119^{2^3}$ & \cellcolor{dunkelgrau}$119^{2^4}$ & $119^{2^5}$ & $119^{2^6}$ & \cellcolor{dunkelgrau}$119^{2^7}$\\
\hline
\cellcolor{dunkelgrau}$119$ & \cellcolor{dunkelgrau}$119^2 \equiv 246$ & $246^2 \equiv 49$ & $49^2 \equiv 124$ & \cellcolor{dunkelgrau}$124^2 \equiv 196$ & $196^2 \equiv 213$ & $213^2 \equiv 82$ & \cellcolor{dunkelgrau}$82^2 \equiv 146$\\
\hline 
\end{tabular}
\end{center}

Somit ist $119 ^ {147} \tmod 253 = 119 ^ {2 ^ 7} \cdot 119 ^ {2 ^ 4} \cdot 119 ^ {2 ^ 1} \cdot 119 ^ {2 ^ 0} \equiv 119 \cdot 246 \cdot 196 \cdot 146 \tmod 253 \equiv 179 \cdot 196 \cdot 146 \tmod 253 \equiv 170 \cdot 146 \tmod 253 \equiv 26 \tmod 253$.

Der Klartext ist damit 

\begin{center}
\uuline{$m = 26$}
\end{center}

Betrachtet man die vorangegangene Verschlüsselung, so sieht man, dass dies genau der Wert ist, der verschlüsselt wurde.

\subsubsection{Sicherheit}

Da das RSA-Verfahren ein Public-Key-Verfahren ist, muss es praktisch unmöglich sein, den privaten Schlüssel $d$ aus dem öffentlichen Schlüssel $(n, e)$ zu berechnen. Die Bestimmung des privaten Schlüssels $d$ aus dem öffentlichen Schlüssel $(n, e)$ ist genauso schwierig wie die Zerlegung des RSA-Moduls in seine Primfaktoren. Somit erfolgt eine Sicherheitsreduktion auf das mathematische Problem der Faktorisierung natürlicher Zahlen, das als sehr schwierig gilt und von allgemeinem Interesse ist.

Es ist auch möglich, dass RSA auf einfachere Weise angegriffen werden kann. Deshalb ist es wichtig, auch andere asymmetrische Verfahren zu betrachten.

Um die Faktorisierung des \textbf{RSA-Moduls} möglichst schwierig zu gestalten werden die beiden Primfaktoren $p$ und $q$ etwa gleich groß gewählt. Die beiden Zahlen sollten zufällig und möglichst gleich-verteilt gewählt werden. Die Schlüssellänge wird bei RSA als Bitlänge des RSA-Moduls angegeben. Gebräuchliche Werte sind 1024 oder 2048.

Der \textbf{Verschlüsselungsexponent} $e$ wird so gewählt, dass die Verschlüsselung effizient möglich ist ohne die Sicherheit zu gefährden. Der kleinste mögliche Wert ist $e = 3$. Dieser ist anfällig gegen sog. \glqq Low Exponent Attacken\grqq. Ein üblicher Wert ist $e = 2 ^ {16} + 1 = 65537$.

Wird das RSA-Verfahren in der Praxis eingesetzt, so muss der \textbf{Entschlüsselungsexponent} $d$ geschätzt gespeichert werden. Die erfolgt beispielsweise auf einer Chipkarte, auf der auch die Entschlüsselung durchgeführt wird damit der Schlüssel die Chipkarte nicht verlassen muss. Zur Beschleunigung der Entschlüsselung könnte der Entschlüsselungsexponent $d$ klein gewählt werden und daraus der passende Verschlüsselungsexponent $e$ berechnet werden. Es wurde aber gezeigt, dass das RSA-Verfahren gebrochen werden kann, wenn $d < n ^ {0,292}$ ist. Generell ist die Größe des Entschlüsselungsexponenten von Bedeutung für den Aufwand der Entschlüsselung.